﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ZoambieGaem
{
    class BinaryHeap {
        public int nodes;
        public Node[] list;

        public BinaryHeap() {
            list = new Node[Maps.height*Maps.width];
            this.nodes = 0;
        }


        public void Add(Node n) {
            this.list[this.nodes+1] = n;
            //nodes++;
            try {
                int bubbleIndex = this.nodes+1;
                while (bubbleIndex != 1) {
                    int parentIndex = bubbleIndex / 2;
                    if (this.list[bubbleIndex].f <= this.list[parentIndex].f) {
                        Node tmpValue = this.list[parentIndex];
                        this.list[parentIndex] = this.list[bubbleIndex];
                        this.list[bubbleIndex] = tmpValue;
                        bubbleIndex = parentIndex;
                    }
                    else {
                        break;
                    }
                }
                this.nodes++;
            }
            catch (Exception e) { Console.WriteLine("## HEAP ADD FAILED -- " + e.ToString()); }
            
        }



        public Node First() {
            
            Node returnItem = this.list[1];
            int position = 1;
            int lowestIndex = 999999;
            Boolean ready = false;
            int f1 = 999999;
            int f2 = 999999;
            this.list[1] = this.list[this.nodes];
            this.list[this.nodes] = null;

            this.nodes--;
            if (!empty()) {
                do {
                    //Console.WriteLine("## SWAPPING " + nodes + " " + swapItem + " " + parent + " " + list.Count());
                    //try {
                    if (position * 2 < nodes)
                        f1 = this.list[position * 2].f;
                    else
                        f1 = 99999;
                    if (position * 2 + 1 < nodes)
                        f2 = this.list[position * 2 + 1].f;
                    else
                        f2 = 99999;

                        

                        if (f1 < this.list[position].f || f2 < this.list[position].f) {
                            if (f2 < f1)
                                lowestIndex = position * 2 + 1;
                            else
                                lowestIndex = position * 2;
                            //Console.WriteLine("## SWAPPING this " + lowestIndex + " to" + position);
                            Node tmpIndex = this.list[lowestIndex];
                            this.list[lowestIndex] = this.list[position];
                            this.list[position] = tmpIndex;
                            position = lowestIndex;

                        }
                        else {
                            ready = true;
                        }
                    //}
                    //catch (Exception e) { Console.WriteLine("## HEAP FIRST-SORT FAILED with low "+ lowestIndex +" pos " + position + "-- " + e.ToString()); }

                } while (!ready);
            }
            return returnItem;
        }




        public Boolean empty() {
            if (list[1] == null)
                return true;
            else
                return false;
        }





        public Boolean findAndUpdate(Node node) {
            Boolean found = false;
            int startIndex = 0;
            
            if (!empty()) {
                for (int i = 1; i < nodes + 1; i++) {
                    try {
                        if (node.x == this.list[i].x && node.y == this.list[i].y) {
                            found = true;
                            if (this.list[i].g > node.g) {
                                startIndex = i;
                                this.list[i] = node;
                            }
                        }
                    }
                    catch (Exception e) { Console.WriteLine("## HEAP FIND_AND_UPDATE FAILED -- " + e.ToString()); }
                }
            }
            if (startIndex > 0) {
                try {
                    int bubbleIndex = startIndex;
                    while (bubbleIndex != 1) {
                        int parentIndex = bubbleIndex / 2;
                        if (this.list[bubbleIndex].f <= this.list[parentIndex].f) {
                            Node tmpValue = this.list[parentIndex];
                            this.list[parentIndex] = this.list[bubbleIndex];
                            this.list[bubbleIndex] = tmpValue;
                            bubbleIndex = parentIndex;
                        }
                        else {
                            break;
                        }
                    }
                }
                catch (Exception e) { Console.WriteLine("## HEAP FIND_SORT FAILED -- " + e.ToString()); }
            }

            return found;
        }






        public Boolean find(Node node) {
            Boolean result = false;
            if (!empty()) { // && node != null
                for (int i = 1; i < nodes; i++) {
                    try {
                        if (node.x == this.list[i].x && node.y == this.list[i].y)
                            result = true;
                    }
                    catch (Exception e) { Console.WriteLine("## HEAP FIND FAILED -- " + e.ToString()); }
                }
            }
            return result;
        }





        public void statics() {
            Console.WriteLine("## NODE AMOUNT " + nodes);
            for (int i = 1; i < nodes + 1; i++) {
                Console.WriteLine("## NODE ind:" + i + " f:" + list[i].f + " g:" + list[i].g + " h:" + list[i].h);
            }
        }

    }

    
}